/*
 * @Author: your name
 * @Date: 2021-10-16 09:48:28
 * @LastEditTime: 2021-10-16 10:02:33
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \luogu\动态规划\模板问题\复习代码\1048.cpp
 */
#include<iostream>
#include<algorithm>
using namespace std;

int f[110][1010];
int ff[1010];

int v[110],m[110];
int main(){
    int T,M;
    //总时间 总数目
    cin >> T >> M;
    for(int i=1; i<=M; i++){
        int a,b;
        cin >> a >> b;
        v[i] = a;
        m[i] = b;
        for(int j=0; j<=T; j++){
            f[i][j] = f[i-1][j];
            if(j >= v[i]) f[i][j] = max(f[i-1][j-v[i]]+m[i],f[i-1][j]);
        }
        for(int j=T; j>=v[i]; j--){
            ff[j] = max(ff[j],ff[j-v[i]]+m[i]);
        }
    }
    cout << f[M][T] << endl;
    cout << ff[T] << endl;
    return 0;
}
